package com.zwj.interview.排序;

import java.util.Arrays;

/**
 * 输入两个数组arr1和arr2，其中数组arr2中的每个数字都唯一，并且都是数组arr1中的数字。
 * 请将数组arr1中的数字按照数组arr2中的数字的相对顺序排序。
 * 如果数组arr1中的数字在数组arr2中没有出现，那么将这些数字按递增的顺序排在后面。
 * 假设数组中的所有数字都在0到1000的范围内。例如，输入的数组arr1和arr2分别是[2，3，3，7，3，9，2，1，7，2]和[3，2，1]，
 * 则数组arr1排序之后为[3，3，3，2，2，2，1，7，7，9]
 */
public class 两队数组相对顺序输出 {

    //使用一个辅助数组来记录每位每个数字出现的次数，每个数字出现的次数恰好就是在他下标处的元素
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        //使用一个辅助数组记录arr1中每个数字出现的次数,新数组的下标代表原数组中的元素，新数组中的元素表示原数组中值的个数
        int[] counts = new int[1001];
        //数组中每个元素，表示该下标对应的数字出现的次数
        for (int num : arr1) {
            counts[num]++;
        }
        int i = 0;
        //根据arr2中数字的顺序来输出数字
        for (int num : arr2) {
            while (counts[num] > 0) {
                arr1[i++] = num;
                counts[num]--;
            }
        }
        //再将剩下的数字进行排序输出
        for (int num = 0; num < counts.length; num++) {
            while (counts[num] > 0) {
                arr1[i++] = num;
                counts[num]--;
            }
        }
        return arr1;
    }



    public static void main(String[] args) {
        System.out.println(Arrays.toString(new 两队数组相对顺序输出().relativeSortArray(new int[]{2,3,3,7,3,9,2,1,7,2},new int[]{3,2,1})));
    }
}
